package graph;

import java.util.*;

/*
 *@description 克隆图
 *@author hkfan
 *@version 1.0
 *@create 2025/6/16 15:36
 */
public class LeetCode_133 {

    class Node {
        public int val;
        public List<Node> neighbors;
        public Node() {
            val = 0;
            neighbors = new ArrayList<Node>();
        }
        public Node(int _val) {
            val = _val;
            neighbors = new ArrayList<Node>();
        }
        public Node(int _val, ArrayList<Node> _neighbors) {
            val = _val;
            neighbors = _neighbors;
        }
    }

    class TempNode {
        Integer start;
        Integer end;

        public TempNode(Integer start, Integer end) {
            this.start = start;
            this.end = end;
        }


    }


    public Node cloneGraph(Node node) {
        if (node==null){
            return null;
        }
        //1. 新建map，key为node的所有值
        HashMap<Integer, Node> nodeMap = new HashMap<>();
        HashMap<Integer, Set<Integer>> edgeMap = new HashMap<>();
        Queue<Node> queue = new LinkedList<>();
        queue.add(node);
        nodeMap.put(node.val,new Node(node.val));
        while (!queue.isEmpty()){
            Node node1 = queue.poll();
            for (Node neighbor : node1.neighbors) {
                if (!nodeMap.containsKey(neighbor.val)){
                    nodeMap.put(neighbor.val,new Node(neighbor.val));
                    queue.add(neighbor);
                }
                Set<Integer> set = edgeMap.getOrDefault(node1.val, new HashSet<>());
                set.add(neighbor.val);
                edgeMap.put(node1.val,set);
            }
        }

        //2. 添加边
        for (Integer startValue : edgeMap.keySet()) {
            for (Integer toValue : edgeMap.get(startValue)) {
                Node node1 = nodeMap.get(startValue);
                Node node2 = nodeMap.get(toValue);
                node1.neighbors.add(node2);
            }
        }
        return nodeMap.get(node.val);

    }




}
